#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x), next(nullptr){}
};

class Solution{
    public:
    ListNode* ans1(ListNode* list1, ListNode* list2){
        ListNode* head = nullptr;
        ListNode* tail = nullptr;
        while(list1 || list2){
            int temp;
            if(list1 && list2){
                if(list1->val >= list2->val){
                    temp = list2->val;
                    list2 = list2->next;
                }else{
                    temp = list1->val;
                    list1 = list1->next;
                }
            }
            else if(list1 == nullptr){
                temp = list2->val;
                list2 = list2->next;
            }
            else if(list2 == nullptr){
                temp = list1->val;
                list1 = list1->next;
            }else{
                break;
            }

            if(!head){
                head = tail = new ListNode(temp);
            }else{
                tail->next = new ListNode(temp);
                tail = tail->next;
            }
        }
        return head;
    }
    
};

void test1(){
    ListNode* list1_head = nullptr;
    ListNode* list1_tail = nullptr;
    vector<int> list1 = {1,2,4};
    for(int i = 0; i != list1.size(); i++){
        if(!list1_head){
            list1_head = list1_tail = new ListNode(list1[i]);
        }else{
            list1_tail->next = new ListNode(list1[i]);
            list1_tail = list1_tail->next;
        }
    }

    ListNode* list2_head = nullptr;
    ListNode* list2_tail = nullptr;
    vector<int> list2 = {1,3,4};
    for(int i = 0; i != list1.size(); i++){
        if(!list2_head){
            list2_head = list2_tail = new ListNode(list2[i]);
        }else{
            list2_tail->next = new ListNode(list2[i]);
            list2_tail = list2_tail->next;
        }
    }

    Solution s;
    ListNode* ret = s.ans1(list1_head, list2_head);
    while(ret != nullptr){
        cout << ret->val << " " << ends;
        ret = ret->next;
    }
    cout << endl;
}


int main(void){
    test1();

    return 0;
}